package com.xypower.tree;

import java.util.Stack;

//是否为二叉搜索树
public class TestBST {
    public static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int data) {
            this.value = data;
        }
    }

    public static  int preValue = Integer.MIN_VALUE;
    //递归方法中序遍历
    public static boolean checkBST(Node head){
        if (head == null){
            return true;
        }
        boolean isLeftBst = checkBST(head.left);
        if (!isLeftBst){
            return false;
        }
        if (head.value <= preValue){
            return false;
        }else {
            preValue = head.value;
        }
        return checkBST(head.right);
    }

//    public static boolean checkBST2(Node head){
//        List<Node> inOrderList = new ArrayList<>();
//        process2(head,inOrderList);
//        //遍历List看是否是升序
//    }
//
//    public  static void process2(Node head,List<Node> inOrderList){
//        if (head == null){
//            return;
//        }
//        process2(head.left,inOrderList);
//        inOrderList.add(head);
//        process2(head.right,inOrderList);
//    }


    public static boolean checkBST3(Node head){
        if (head != null){
            int preValue = Integer.MIN_VALUE;
            Stack<Node> stack = new Stack<Node>();
            while (!stack.isEmpty() || head!=null){
                if (head!=null){
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    if (head.value <= preValue){
                        return false;
                    }else {
                        preValue = head.value;
                    }

                    head = head.right;
                }
            }
        }
        return true;
    }


//可能性解决

    public static class ReturnData{
            public boolean isBST;
            public int min;
            public int max;

        public ReturnData(boolean is,int mi,int ma) {
            isBST = is;
            min = mi;
            max = ma;
        }
    }
    public static ReturnData process(Node x){
        if (x==null){
            return null;
        }
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);
        int min=x.value;
        int max=x.value;
        if (leftData!=null){
            min = Math.min(min,leftData.min);
            max = Math.max(max,leftData.max);
        }
        if (rightData!=null){
            min = Math.min(min,rightData.min);
            max = Math.max(max,rightData.max);
        }


//        boolean isBST=true;
//        if (leftData!=null && (leftData.isBST || leftData.max >= x.value)){
//            isBST = false;
//        }
//        if (rightData!=null && (rightData.isBST || x.value >= rightData.min)){
//            isBST = false;
//        }

        boolean isBST = false;
        if (
                (leftData!=null ? (leftData.isBST && leftData.max < x.value) : true)
                    &&
                (rightData!=null ? (rightData.isBST && rightData.min > x.value) : true)
        ){
            isBST = true;
        }

        return new ReturnData(isBST,min,max);
    }


//满二叉树
    public static boolean isF(Node head){
        if (head == null){
            return true;
        }
        Info data = f(head);
        return data.nodes == (1 << data.height -1);
    }

    public static class Info{
        public int height;
        public int nodes;

        public Info(int h,int n ){
            height = h;
            nodes = n;
        }
    }
    public static Info f(Node x){
        if (x == null){
            return new Info(0,0);
        }
        Info leftData = f(x.left);
        Info rightData = f(x.right);
        int height = Math.max(leftData.height,rightData.height)+1;
        int nodes = leftData.nodes + rightData.nodes + 1;
        return new Info(height,nodes);
    }



}
